package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Ghost on 2014/11/7 0007.
 */
public class Palindrome_Partitioning {
    public boolean isPalindrome(String ss){
        char[] s = ss.toCharArray();
        int begin=0, end = s.length-1;
        while(begin<=end){
            if(s[begin] !=s[end])
                return false;
            begin++;
            end--;
        }
        return true;
    }
    public void find(char[] ss,int begin,ArrayList<List<String>> rst, List<String> s){
        if(begin>ss.length)
            return;
        else if(begin == ss.length){
            rst.add(new ArrayList<String>(s));
            return;
        }
        String tmp = "";
        for(int i=begin;i<ss.length;i++){
            tmp = tmp+ss[i];
            if(isPalindrome(tmp)){
                s.add(tmp);
                find(ss,i+1,rst,s);
                s.remove(s.size()-1);
            }
        }
    }
    public List<List<String>> partition(String s) {
        char[] ss = s.toCharArray();
        ArrayList<List<String>> rst = new ArrayList<List<String>>();
        ArrayList<String> tmp = new ArrayList<String>();
        find(ss,0,rst,tmp);
        return rst;
    }
    public static void main(String[] args){
        Palindrome_Partitioning palindrome_partitioning = new Palindrome_Partitioning();
        String s = "aba";
        System.out.println(palindrome_partitioning.partition(s));
    }
}
